package com.algorithms.heap;

import com.algorithms.utils.AlgorithmException;

@SuppressWarnings("unchecked")
public class Heap<T> {
	private HeapNode<T>[] heapList;
	private int maxSize;
	private int currSize;
	
	public Heap(int size){
		this.heapList = new HeapNode[size];
		this.maxSize = size;
		this.currSize = 0;
	}
	
	public int size(){
		return this.currSize;
	}
	
	/**
	 * insert a node into the heap
	 * 
	 * @param key
	 * @param data
	 * @throws AlgorithmException
	 */
	public void insert(int key, T data) throws AlgorithmException{
		if (this.currSize == this.maxSize){
			throw new AlgorithmException("heap is overflow");
		}
		
		// insert new item to the rightmost position
		heapList[this.currSize++] = new HeapNode<T>(key, data);
		
		// start from the rightmost item
		trickleUp(this.currSize - 1);
	}
	
	/**
	 * delete the maximum key node out of the heap
	 * 
	 * @param key
	 * @return
	 * @throws AlgorithmException
	 */
	public T delete() throws AlgorithmException {
		// when heap is empty
		if (this.currSize == 0){
			throw new AlgorithmException("heap is empty");
		}
		
		// when heap has only root node
		if (this.currSize == 1){
			HeapNode<T> node = heapList[0];
			this.currSize = 0;
			return node.getData();
		}
		
		// ------ when heap has more than 1 nodes ------
		// swap the root item with the rightmost item
		T deletedData = heapList[0].getData();
		heapList[0] = heapList[this.currSize-- - 1];
		
		// trickle down the root item
		trickleDown(0);
		
		return deletedData;
	}
	
	/**
	 * move up an item from its current index to its parents on the 
	 * tree until it finds a bigger value
	 * 
	 * @param index
	 */
	public void trickleUp(int index){
		int cIdx = index;
		HeapNode<T> bottom = heapList[cIdx];
		// get parent index
		int pIdx = (cIdx - 1) / 2;

		// move up to find the appropriate position 
		while(cIdx > 0 && 
			bottom.getKey() > heapList[pIdx].getKey()){
			// check if we should move up to the parent node
			// list is pull down 
			heapList[cIdx] = heapList[pIdx];
				
			// moves up to parent
			cIdx = pIdx;
			pIdx = (cIdx - 1) / 2;
		}
		
		heapList[cIdx] = bottom;
	}
	
	public void trickleDown(int index){
		// current index
		int cIdx = index;
		HeapNode<T> root = heapList[index];

		//left child index and right child index
		int lChIdx, rChIdx;

		while (cIdx <= (this.currSize - 1) / 2){
			
			// get children nodes
			lChIdx = cIdx * 2 + 1;
			rChIdx = lChIdx + 1;
			
			// when left & right children are not available
			if (lChIdx > this.currSize - 1){
				break;
			}
						
			// when only left child node available
			if (lChIdx == this.currSize - 1){
				if (root.getKey() < heapList[lChIdx].getKey()){
					// swap if current node has key smaller than 
					// its left child node
					heapList[cIdx] = heapList[lChIdx];
				}					
				break;
			}
			
			// when both children are available
			// if current node should be swapped with the left child
			if (root.getKey() < heapList[lChIdx].getKey() && 
				heapList[lChIdx].getKey() >= heapList[rChIdx].getKey()){
				
				heapList[cIdx] = heapList[lChIdx];

				// moves download to the left child 
				cIdx = lChIdx;
				continue;
			}
			
			// if current node should be swapped with the right child
			if (root.getKey() < heapList[rChIdx].getKey() && 
				heapList[lChIdx].getKey() <= heapList[rChIdx].getKey()){
				
				heapList[cIdx] = heapList[rChIdx];
				
				// moves to the right child index
				cIdx = rChIdx;
				continue;
			}	
			
			// no more moves
			break;
		}
		
		// swap the root with the current index
		heapList[cIdx] = root;
	}

	public void printHeap(){
		System.out.println("Heap: ");
		for (int i = 0; i < this.currSize; i++){
			System.out.print(heapList[i].getKey() + ", ");
		}
		System.out.println();
	}
}
